package lanQiaoBei.数学知识.欧拉函数;

import java.io.*;
import java.util.*;

/*筛法求欧拉函数 https://blog.csdn.net/qq_62417282/article/details/128742135(解析)
*给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1≤n≤1e6

输入样例：

6
输出样例：

12
* */
public class P2 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final static int N = 1000010;
    static int primers[] = new int[N], phi[] = new int[N], cnt;
    static boolean st[] = new boolean[N];

    static void scan() throws Exception {

    }

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(br.readLine());

        phi[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primers[cnt++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; primers[j] <= n / i; j++) {
                st[primers[j] * i] = true;
                if (i % primers[j] == 0) {
                    phi[primers[j] * i] = phi[i] * primers[j];
                    break;
                } else {
                    phi[primers[j] * i] = phi[i] * (primers[j] - 1);
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += phi[i];
        }
        System.out.print(res);
    }
}
